<HTML>
<HEAD>
<TITLE>PVM Definition</TITLE>
</HEAD>

<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H1>PVM Definition</H1>
<H3>David Nordstrom
<BR>George Mason University</H3>
</CENTER>

<P><P>PVM (for PAXI Virtual Machine) is a very simple architecture intended
to provide an emulated target machine for PAXI compilers.  Its consists of:

<UL>
<LI>memory
<LI>a set of registers</LI>
<LI>a simple instruction set</LI>
<LI>a fetch-execute cycle</LI>
</UL>

<P><H3>Memory</H3>

Memory is emulated by two integer arrays, the <EM>code store</EM> and
the <EM>data store</EM>.  Instructions are stored in the code store
beginning at location 0.  Data (integers and character strings) are
stored in the data store.

<P>The first 500 locations of the data store are used as the system
stack.  The stack pointer SP holds the address of the top of stack
item.  (Notice that for a non-empty stack this means that SP holds the
address of an occupied position, <EM>not</EM> the next available free
position.)  The stack grows downwards in memory (i.e. towards lower
addresses) so the "top" of stack is the <EM>lowest</EM> occupied stack
location.

<P><H3>Registers</H3>

There is an (integer) <EM>instruction pointer</EM>, IP, which holds
the address of the next instruction to be executed.  Here an "address"
is simply an integer index into the the code store array.  There is
also a <EM>register array</EM> consisting of three integers.  Register
0 is used as the <EM>stack pointer</EM>, SP, which always points to
the top of the system stack.

<P><H3>The PVM Instruction Set</H3>

All PVM instructions consist of three integers: an opcode and two
arguments.  In the following table, under arguments, D and E are
indexes into the data store, R and S are register numbers (indexes
into the register array), A is an index into the code store, and N is
a constant.  If an argument is not used a 0 appears in its place.  The
<EM>mnemonics</EM> are for convenience -- only the opcodes are
understood by a PVM emulator.

<P>
<TABLE border = 2>
<THEAD>
<TR>
<TD>Opcode<TD>Mnemonic<TD>Arguments<TD> Description
<TBODY>
<TR>
<TD> 1
<TD> mov
<TD> D, E
<TD> Move - copy value from E to D in data store

<TR>
<TD> 2
<TD> mvi
<TD> D, N
<TD> Move immediate - put constant value N in D in data store

<TR>
<TD> 3
<TD> mif
<TD> D, E
<TD> Move indirect from - copy with source indirect and destination direct

<TR>
<TD> 4
<TD> mit
<TD> D, E
<TD> Move indirect to - copy with source direct and destination indirect

<TR>
<TD> 5
<TD> lri
<TD> R, N
<TD> Load register immediate - put constant value N in register R

<TR>
<TD> 6
<TD> ldr
<TD> R, D
<TD> Load register - copy value from D in data store to register R

<TR>
<TD> 7
<TD> str
<TD> D, R
<TD> Store register - copy value from register R to D in data store

<TR>
<TD> 8
<TD> mvr
<TD> R, S
<TD> Move register - copy value from register S to register R

<TR>
<TD> 9
<TD> add
<TD> D, E
<TD> Add - add values in D and E in data store and leave sum in D

<TR>
<TD> 10
<TD> addri
<TD> R, N
<TD> Add register immediate - add constant N to value in register R

<TR>
<TD> 11
<TD> sub
<TD> D, E
<TD> Subtract - subtract value in E from value in D in data store and
leave difference in D

<TR>
<TD> 12
<TD> mul
<TD> D, E
<TD> Multiply - multiply values in D and E in data store and leave
product in D

<TR>
<TD> 13
<TD> div
<TD> D, E
<TD> Divide - divide value in D by value in E in data store and leave
quotient in D

<TR>
<TD> 14
<TD> or
<TD> D, E
<TD> Or - leave OR of Boolean values in D and E in data store in D

<TR>
<TD> 15
<TD> and
<TD> D, E
<TD> And - leave AND of Boolean values in D and E in data store in D

<TR>
<TD> 16
<TD> not
<TD> D, 0
<TD> Not - replace value in data store at D with its logical complement

<TR>
<TD> 17
<TD> b
<TD> A, 0
<TD> Branch - transfer control to location A in code store

<TR>
<TD> 18
<TD> beq
<TD> A, D
<TD> Branch on equal - if value at D in data store is zero branch to A
in code store

<TR>
<TD> 19
<TD> bne
<TD> A, D
<TD> Branch on not equal - if value at D in data store is not zero
branch to A in code store

<TR>
<TD> 20
<TD> bgt
<TD> A, D
<TD> Branch on greater than - if value at D
in data store is &gt; 0 branch to A in code store

<TR>
<TD> 21
<TD> bge
<TD> A, D
<TD> Branch on greater than or equal - if
value at D in data store is &gt;= 0 branch to A in code store

<TR>
<TD> 22
<TD> blt
<TD> A, D
<TD> Branch on less than - if value at D in
data store is &lt; 0 branch to A in code store

<TR>
<TD> 23
<TD> ble
<TD> A, D
<TD> Branch on less than or equal - if
value at D in data store is &lt;= 0 branch to A in code store

<TR>
<TD> 24
<TD> pushd
<TD> D, 0
<TD> Push data - push value at D in data store onto the stack

<TR>
<TD> 25
<TD> pushr
<TD> R, 0
<TD> Push register - push value from register R onto the stack

<TR>
<TD> 26
<TD> pushi
<TD> N, 0
<TD> Push immediate - push constant N onto the stack

<TR>
<TD> 27
<TD> popd
<TD> D, 0
<TD> Pop data - pop top of stack into data store at location D

<TR>
<TD> 28
<TD> popr
<TD> R, 0
<TD> Pop register - pop top of stack into register R

<TR>
<TD> 29
<TD> puti
<TD> D, 0
<TD> Put integer - display integer at D in data store

<TR>
<TD> 30
<TD> puts
<TD> D, 0
<TD> Put string - display NULL-terminated string beginning at D in data
store

<TR>
<TD> 31
<TD> line
<TD> 0, 0
<TD> New line -  move cursor to beginning of next line

<TR>
<TD> 32
<TD> geti
<TD> D, 0
<TD> Get integer - accept integer from keyboard and store at D in
data store 

<TR>
<TD> 33
<TD> gets
<TD> D, 0
<TD> Get string - accept string from keyboard and store
NULL-terminated at D in data store 

<TR>
<TD> 34
<TD> call
<TD> A, 0
<TD> Call - push IP and enter the subprogram at A in code store

<TR>
<TD> 35
<TD> ret
<TD> N, 0
<TD> Return - return from subprogram call removing N parameters from
the stack

<TR>
<TD> 36
<TD> stop
<TD> 0, 0
<TD> Stop - end program

</TABLE>

<P><H3>The Move Instructions</H3>

There are a number of move instructions to provide several addressing
modes.  All addresses used by the move instructions are indexes into
the data store.  The <STRONG>mov</STRONG> instruction uses <EM>direct
addressing</EM> for both of its arguments, i.e. they are addresses in
the data store.  <STRONG>mvi</STRONG> uses direct addressing and
<EM>immediate</EM> for its second, i.e. the second argument is a
(constant) value, not an address.

<P>The <STRONG>mif</STRONG> and <STRONG>mit</STRONG> instructions use
indirect addressing.  In indirect addressing a memory location is used
as a pointer.  <STRONG>mif</STRONG> treats its second argument (the
<EM>source</EM>) as a pointer and uses direct addressing for its first
argument (the <EM>target</EM>).  <STRONG>mit</STRONG> treats is first
argument as a pointer and uses direct addressing for its second
argument.

<P>The <STRONG>ldr</STRONG> (load register) and <STRONG>str</STRONG>
(store register) instructions copy values between memory and
registers.  <STRONG>ldr</STRONG> R, D copies the value from data store
D to register R and <STRONG>str</STRONG> D, R copies the value from
register R to data store D. <STRONG>lri</STRONG> R, N (load register
immediate) puts the constant value N into register R.
<STRONG>mvr</STRONG> (move register) is used to copy a value from one
register to another.

<P><H3>The Arithmetic and Logical Instructions</H3>

The arithmetic instructions (except <STRONG>addri</STRONG>) all have the
same format.  The two arguments are addresses in the data store.
<STRONG>sub</STRONG>, D, E, for example, has the meaning:
data_store[D] = data_store[D] - data_store[E].  <STRONG>addri</STRONG>
adds a constant value to a register.

<P>The logical instructions <STRONG>and</STRONG> and
<STRONG>or</STRONG> work in the same manner as the arithmetic
instructions.  <STRONG>not</STRONG> D, 0 replaces data_store[D] with
its logical complement.  These instructions assume the value used for
<EM>true</EM> or <EM>false</EM> is 1 or 0.  The result is undefined
for other values, i.e. if applied to values other than 1 or 0, it
doesn't matter what values are left by <STRONG>and</STRONG>,
<STRONG>or</STRONG>, and <STRONG>not</STRONG>.

<P><H3>The Branching Instructions</H3>

<STRONG>b</STRONG> A, 0 (branch to A) does an <EM>unconditional</EM> transfer
of control to location A in the code store.  It accomplishes this by
putting A into IP.

<P>The remaining branching instructions are all <EM>conditional</EM>
branching instructions.  Each takes two arguments: code store address
A and data store address D.  It compares D to 0 and if a test is
successful transfers control to location A in the code store.  The
test is given by the name of the instruction.  For example
<STRONG>bgt</STRONG> A, D branches to A if data_store[D] is greater
than 0.

<P><H3>The Stack Operation Instructions</H3>

The various push and pop instructions work on the system stack.
Recall that SP points to the top of stack item (in the data store)
rather than the next available free space.  Thus a push instruction
adjusts SP <EM>before</EM> storing a value and a pop instruction
adjusts SP <EM>after</EM> reading a value.  Recall also that the stack
grows downwards in memory so a push instruction <EM>decrements</EM> SP.

<P>There are three push instructions:  <STRONG>pushd</STRONG> pushes a
value from the data store, <STRONG>pushr</STRONG> pushes a register
value, and <STRONG>pushi</STRONG> pushes a constant.  There are two
pop instructions:  <STRONG>popd</STRONG> pops top of stack into the
data store and <STRONG>popr</STRONG> pops top of stack into a register.

<P><H3>The I/O Instructions</H3>

Instead of calling operating system services PVM supplies several
instructions to do (very) basic input and output.

<P><STRONG>puti</STRONG> D, 0 displays the <EM>integer</EM> stored at
data_store[D] and <STRONG>geti</STRONG> D, 0 accepts an integer from the
keyboard and stores it in data_store[D].  <STRONG>line</STRONG>
displays newline (i.e. moves the cursor to the beginning of the next
line).

<P><STRONG>gets</STRONG> and <STRONG>puts</STRONG> do character string
input and output.  A <EM>string</EM> is stored in the data store as an
array of ASCII codes terminated by a 0.  Each ASCII code is stored in
<EM>one integer position</EM> in the data store since "byte" has no
meaning in PVM.

<P><STRONG>puts</STRONG> D, 0 displays the string beginning at D in
the data store.  <STRONG>gets</STRONG> D, 0 accepts a string from the
keyboard and stores it, with a 0 terminator, in the data store
beginning at D.  <STRONG>gets</STRONG> accepts all characters entered
up to the point where the user hits the enter key.  This means that
<STRONG>gets</STRONG> behaves like "cin.getline()" rather than "cin
>>".  It does <EM>not</EM> store a newline (ASCII 10) at the end of
the string.

<P><H3>Call and Return</H3>

<STRONG>call</STRONG> A, 0 makes a call to the subprogram at (code
store) address A.  It pushes IP onto the stack and then copies A into
IP.  <STRONG>ret</STRONG> N, 0 returns from a subprogram call and
clears N parameters from the stack.  It pops top of stack into IP and
then <EM>adds</EM> N to SP.

<P><H3>Stop</H3>

The <STRONG>stop</STRONG> instruction terminates a running program and
exits PVM.

<P><H3>The Fetch-Execute Cycle</H3>

PVM runs programs using the classical <EM>fetch-execute cycle</EM>.
This is a loop repeating the following steps <EM>in this order</EM>:

<UL>
<LI> Fetch:  read from memory the instruction pointed to by IP.
<LI> Increment:  increment IP to point to the <EM>next
instuction</EM>, i.e. add 3 to IP.
<LI> Execute: execute the fetched instruction.
</UL>

Notice that when an instruction is being executed IP does not point to
that instruction but to the instruction which follows it.

</HTML>
